package com.algorithm.liyc.practice;


import java.util.ArrayList;
import java.util.List;

import static java.lang.Math.min;

/**
 * 查找常用字符
 * 给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
 *
 * @author Liyc
 * @date 2023/11/28 14:05
 **/

public class Solution15 {
    /**
     *
     */
    public List<String> commonChars(String[] A) {
        List<String> result = new ArrayList<>();
        if (A.length == 0) return result;
        // 用来统计所有字符串里字符出现的最小频率
        int[] hash = new int[26];
        // 用第一个字符串给hash初始化
        for (int i = 0; i < A[0].length(); i++) {
            hash[A[0].charAt(i) - 'a']++;
        }
        // 统计除第一个字符串外字符的出现频率
        for (int i = 1; i < A.length; i++) {
            int[] hashRecord = new int[26];
            for (int j = 0; j < A[i].length(); j++) {
                hashRecord[A[i].charAt(j) - 'a']++;
            }
            // 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
            for (int k = 0; k < hash.length; k++) {
                hash[k] = min(hash[k], hashRecord[k]);
            }
        }
        // 将hash统计的字符次数，转成输出形式
        for (int i = 0; i < hash.length; i++) {
            while (hash[i] != 0) { // 注意这里是while，多个重复的字符
                char a = (char) (i + 'a');
                result.add(String.valueOf(a));
                hash[i]--;
            }
        }
        return result;
    }
}
